//寻找加法交换序列 n = 3 ，m = 2 * r + 1
//该序列第一行：-r，-r + 1, ... , 0 , 1, 2, ... ,r-1, r
//剩余的两行都是： 第一行的全排列
//该三行中任意两行的差都是第一行的全排列
//输入m的值，输出符合要求的矩阵，并且要给出验证的过程

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <fstream>
#include <ctime>

using namespace std;
int r;
vector<int> aps1;

//输出数组函数
void output_vec(const vector<int> &a)
{
    for(auto i : a){
        cout<<i<<"  ";
    }
    cout<<endl;
}

//根据目前所确定的值，判断新值是否符合要求
//数组初始化为r+1，所有非r+1的值都是确定的值
bool check(const vector<int> &now, int pos, int x){
    //1.不能与已有元素重复
    //2.与已有元素的差值不能等于位置的差值，带符号的，保证不存在相同的差值
    //3.与aps1对应的位置上的值的差属于-r，r
    if(find(now.begin(), now.end(), x) != now.end()){
        //cout<<"1"<<endl;
        return false;
    }
    for(int i = 0; i<now.size() ;++i){
        if((now[i]!=r+1) && (x-now[i] == pos-i)){
            //cout<<"2"<<endl;
            return false;
        }
    }
    if(aps1[pos]-x<-r || aps1[pos]-x>r){
        //cout<<"3"<<endl;
        return false;
    }
    return true;
}

//得到一个序列：aps2
//len代表遍历的深度，也可以说是当前的确定的元素下标记
//不过当前状态下，一个深度下有两个元素要确定，因为它们的范围对称
//当未找到解时，返回一个原状态数组数组，当len = m/2时，说明到头了
bool get_sequence(vector<int> &a, int len){
    int m = a.size();
    if(len>m/2){
        return true;
    }
    vector<int> temp;
    temp.assign(a.begin(), a.end());
    // cout<<"len: "<<len<<", 改前: "<<endl;
    // output_vec(a);
    if (len != m / 2)
    {
        for (int i = -r; i <= len; ++i)
        {
            if (check(a, len, i))
            {
                //cout<<i<<" ";
                a[len] = i;
                for (int j = -len; j <= r; ++j)
                {
                    if (check(a, m - 1 - len, j))
                    {
                        //cout<<j<<" ";
                        a[m - 1 - len] = j;
                        // cout<<"改后: ";
                        // output_vec(a);
                        //cout << "len:" << len << "    此时i:" << i << "   j:" << j << endl;
                        if (get_sequence(a, len + 1))
                        {
                            return true;
                        }
                    }
                }
                a[m - 1 - len] = r+1;
            }
        }
    }else{
        for(int i=-r; i<=r; ++i){
            if(check(a, len, i)){
                a[len] = i;
                return true;
            }
        }
    }

    //没有返回成功，说明找不到解了， 该把数组状态改回初始
    a.assign(temp.begin(),temp.end());
    return false;
}

bool isfirst = true;        //判断当前是否是第一次到达根节点, 当更换aps2时才重新置为真
//得到序列aps3 如果返回true，此时aps2与aps3都是符合标准的
//先按得到aps2的方法得到一个与aps2不同的序列aps3，并存储下来
//连续的
bool get_sequence_aps3(const vector<int> &a2, vector<int> &a3,int len){
    int m = a2.size();
    if(len>m/2){
        return true;
    }
    vector<int> temp;
    temp.assign(a3.begin(), a3.end());
    int exi = -r;
    int exj = -len;
    if(len == 0) {
        exi = a2[len];
        //exj = a2[m-1-len];
    }else if(isfirst){      //第一次到达这一层 也是由于保存了上一层的信息，所以a3第一次一定能到最底层的节点
        exi = a2[len];
    }
    if(len != m/2){
        for (int i=exi; i<=len; ++i){
            if(check(a3, len, i)){
                a3[len] = i;
                if(i == exi && len == 0){
                    exj = a2[m-1-len] ;
                }else if(i == exi && isfirst){
                    exj = a2[m-1-len];
                }else{
                    exj = -len;
                }
                for(int j=exj; j<=r; ++j){
                    // if(a3[0] == -3 && a3[m-1] == 2){
                    //     cout<<"hahah"<<endl;
                    // }
                    if(check(a3, m-1-len, j)){
                        a3[m-1-len] = j;
                        //cout << "len:" << len << "    此时i:" << i << "   j:" << j << endl;
                        if(get_sequence_aps3(a2, a3, len + 1)){
                            return true;
                        }
                    }
                }
                a3[m-1-len] = r+1;
            }
        }
    }else{  //最后一个点，赋值完成后，看其于x2是否相等 如果是第一次到达，则其从x2的下一个位置开始  后面到达的，都不是第一次都要从头开始
        int left = -r;
        if(isfirst){
            left = a2[len] + 1;
            isfirst = false;
        }
        for(int i=left; i<=r; ++i){
            if(check(a3, len, i)){
                a3[len] = i;
                if(a2==a3)
                {
                    a3.assign(temp.begin(),temp.end());
                    return false;
                } 
                return true;
            }
        }
    }

    //没有返回成功，说明找不到解了， 该把数组状态改回初始
    a3.assign(temp.begin(),temp.end());
    return false;
    
}

//如果当前于a2对应位置相同的值的个数 >= 2 返回false
//不能超过1
bool check_aps3(const vector<int> &a2, const vector<int> &a3){
    int count = 0;
    for(int i=0; i<a2.size(); ++i){
        if(a2[i] == a3[i]) ++count;
        if(count>1) return false;
    }
    return true;
}

//寻找一个与已知集合中不同的序列
//在已知一个x2的情况下，寻找合理的x3
//不连续的
bool test_get_sequence_aps3(const vector<int> &a2, vector<int> &a3,int len){
    int m = a2.size();
    if(len>m/2){
        return true;
    }
    vector<int> temp;
    temp.assign(a3.begin(), a3.end());
    int exi = -r;
    int exj = -len;
    if(len == 0) {
        exi = a2[len];
        //exj = a2[m-1-len];
    }
    if(len != m/2){
        for (int i=exi; i<=len; ++i){
            if(check(a3, len, i)){
                a3[len] = i;
                if(!check_aps3(a2, a3)){
                    a3[len] = r+1;
                    continue;
                }
                if(i == exi && len == 0){
                    exj = a2[m-1-len] ;
                }else{
                    exj = -len;
                }
                for(int j=exj; j<=r; ++j){
                    if(check(a3, m-1-len, j)){
                        a3[m-1-len] = j;
                        if(!check_aps3(a2, a3)){
                            a3[m-1-len] = r+1;
                            continue;
                        }
                        //cout << "len:" << len << "    此时i:" << i << "   j:" << j << endl;
                        if(test_get_sequence_aps3(a2, a3, len + 1)){
                            return true;
                        }
                    }
                }
                a3[m-1-len] = r+1;
            }
        }
    }else{  //最后一个点，赋值完成后，看其于x2是否相等 如果是第一次到达，则其从x2的下一个位置开始  后面到达的，都不是第一次都要从头开始
        for(int i=-r; i<=r; ++i){
            if(check(a3, len, i)){
                a3[len] = i;
                if(a2==a3)
                {
                    a3.assign(temp.begin(),temp.end());
                    return false;
                } 
                return true;
            }
        }
    }

    //没有返回成功，说明找不到解了， 该把数组状态改回初始
    a3.assign(temp.begin(),temp.end());
    return false;
}

//验证aps2和aps3的差是否符合标准，
bool test(const vector<int> &a2, const vector<int> &a3)
{
    int m = a2.size();
    vector<int> ans;
    for(int i=0; i<m; ++i){
        int temp = a2[i]-a3[i];
        //保证符合范围
        if(temp>r || temp<-r){
            return false;
        }
        //保证不重复
        if(find(ans.begin(), ans.end(), temp)!=ans.end()){
            return false;
        }
        ans.push_back(temp);
    }
    if(ans.size() != a2.size()){
        return false;
    }
    return true;
}

//int coutofseq=0;
vector<vector<int>> apslist;
//isfirst此时已经是 false状态了
//先验证x2与x3是否符合，如果不符合，继续寻找aps3 
//当尝试了所有可能的aps3后，如果还未找到则，更换aps2为原来的aps3
//再次寻找aps3
//边界为：1.找到符合条件的解 2.寻找了x2的所有可能解，此时x2为最后一个符合条件的序列，此时x3是无法找到的,但这个条件无法作为边界
//所以必须统计所有的符合条件的序列，当深度为序列值时，就说明已经到尽头了
//
//寻找完所有的aps3后，跟换aps2（不加test的），再寻找一个aps3（加test的），然后跟换aps3（不加test）
//当aps2跟换后，找不到aps3则就说明已经到尽头了
bool huisu(vector<int> &a2, vector<int> &a3, int depth)
{
    if(test(a2, a3)) return true;
    int m = a2.size();
    vector<int> newasp(m, r+1);
    if(a3 == newasp) return false;      //此时已找不到aps3

    if(depth == 0) apslist.push_back(a3);

    vector<int> temp1 ,temp2;
    vector<int> temp3(m, r+1);      //存储下一个aps2
    //cout<<"newasp: size:"<<newasp.size()<<" n[0]: "<<newasp[0]<<endl;
    temp1.assign(a2.begin(), a2.end());
    temp2.assign(a3.begin(), a3.end());

    bool flag = true;
    //找到的首个序列要保存作为huisu的第二个参数 
    if(flag){
        temp3.assign(newasp.begin(), newasp.end());
        flag = false;
    }
    //经过这趟循环，可以统计出所有的可能序列 
    //当找不到新a3的情况下， newasp中的值为r+1
    if(depth == 0){
        isfirst = true;         //此时更换了第一参数
        while(get_sequence_aps3(a3, newasp, 0)){
            if(test(a2,newasp)){
                a3.swap(newasp);
                return true;
            }
            apslist.push_back(newasp);
            a3.swap(newasp);
            vector<int> wt (m,r+1);
            newasp.swap(wt);
            isfirst = true;         //此时第一个参数也改变了
        }
    }else{   //此时已经找到所有的从初始aps3开始的所有的序列
    //当跟换了a2和a3后，需找到当前的a3在序列中的位置，然后向后找
    //运行完成后说明此时的a2已经无用了
        int index;
        for(int i=0; i<apslist.size(); ++i){
            if(a3 == apslist[i]){
                index = i+1;
            }
        }
        for(int i=index; i<apslist.size(); ++i){
            if(test(a2,apslist[i])){
                a3.assign(apslist[i].begin(), apslist[i].end());
                return true;
            }
        }
    }
    
    //尝试从第一个a3开始的所有序列中是否有答案
    if(depth == 0){
        for(int i=0; i<apslist.size(); ++i){
            for(int j=apslist.size()-1; j>i; --j){
                if(test(apslist[i],apslist[j])){
                    a2.assign(apslist[i].begin(),apslist[i].end());
                    a3.assign(apslist[j].begin(), apslist[j].end());
                    return true;
                }
            }
        }
    }

    //此时说明当前的aps2是不存在解的
    //如果此aps2存在于序列之中，直接返回false
    //因为所有存在于序列list中的值都尝试过了有没有解 -》并没有
    //所以如果a2遍历到了该list中，说明已经无解了
    for(int i=0 ;i<apslist.size();++i){
        if(a2 == apslist[i]){
            a2.assign(temp1.begin(), temp1.end());
            a3.assign(temp2.begin(), temp2.end()); 
            return false;
        }
    }

    //更换aps2 
    isfirst = true;             //此时第一个参数改变了
    if(get_sequence_aps3(a2, temp3, 0)){
        a2.assign(temp3.begin(), temp3.end());
    }else{
        a2.assign(temp1.begin(), temp1.end());
        a3.assign(temp2.begin(), temp2.end()); 
        return false;
    }
    //跟换aps3
    vector<int> woot(m,r+1);
    a3.swap(woot);
    if(!test_get_sequence_aps3(a2, a3, 0)){
        a2.assign(temp1.begin(), temp1.end());
        a3.assign(temp2.begin(), temp2.end()); 
        return false;
    }
    if(huisu(a2, a3, depth+1)){
        return true;
    }
    a2.assign(temp1.begin(), temp1.end());
    a3.assign(temp2.begin(), temp2.end()); 
    //如果没有符合条件的值，则返回原先的值
    //cout<<"返回失败前"<<endl;
    return false;
}



//文件读写函数
void output(ofstream &out,const vector<int> &a)
{
    for(auto i : a){
        out<<i<<"   ";
    }
    out<<endl;
}

//将计算结果写入
void output_second(ofstream &out, const vector<int> &a, const vector<int> &b, const vector<int> &c)
{
    vector<int> ans;
    out<<"X1-X2: ";
    for(int i=0; i<a.size(); ++i){
        ans.push_back(a[i]-b[i]);
    }
    output(out, ans);
    out<<"X1-X3: ";
    for(int i=0; i<a.size(); ++i){
        ans[i] = a[i]-c[i];
    }
    output(out, ans);
    out<<"X2-X3: ";
    for(int i=0; i<a.size(); ++i){
        ans[i] = b[i]-c[i];
    }
    output(out, ans);
}

int main()
{
    int m,n=3;
    cout<<"请输入m的值:(奇数)"<<endl;
    cin>>m;
    clock_t startTime,endTime;
    startTime = clock();//计时开始
    r = (m-1)/2;
    vector<int> aps2, aps3;

    //生成第一行 初始化其它两行
    for(int i =0; i<m; ++i){        
        aps1.push_back(-r + i);
        aps2.push_back(r+1);
        aps3.push_back(r+1);
    }

    if(get_sequence(aps2, 0)){      //能顺利返回一个序列，解下来判断该数列是否是，符合条件的
        output_vec(aps2);
    }

    if(test_get_sequence_aps3(aps2, aps3, 0)){
        output_vec(aps3);
    }

    //未找到的话就，修改aps2后再找asp3，直到aps2到达尽头
    //又是回溯法，要确定，边界
    //将结果存储进文件
    //两部分：第一：三行数据，标上：x1，x2，x3
    //第二：三行数据，标上：x1-x2，x1-x3，x2-x3
    if(huisu(aps2, aps3, 0)){
        cout<<"find it!"<<endl;
        endTime = clock();//计时结束
        ofstream out("out.txt");
        if(out.is_open()){
            out<<"X1: ";
            output(out, aps1);
            out<<"X2: ";
            output(out, aps2);
            out<<"X3: ";
            output(out, aps3);
            output_second(out, aps1, aps2, aps3);
        } 
    }else{
        cout<<"no result!"<<endl;
        //cout<<coutofseq<<endl;
    }
    cout << "The run time is:" << (double)(endTime - startTime)/CLOCKS_PER_SEC<< "s" << endl;
    return 0;
}